package org.laizili.solution.leetcode;

/**
 * <a href="https://leetcode-cn.com/problems/find-smallest-letter-greater-than-target/">744. 寻找比目标字母大的最小字母</a>
 * <p>
 * tags: 查找; 二分查找
 * </p>
 */
public class Problem744 {
    private static class Solution {
        public char nextGreatestLetter(char[] letters, char target) {
            return upperBound(letters, target);
        }

        private char upperBound(char[] letters, char target) {
            /*左闭右开区间([low, high))二分查找
             *    notes:
             *      循环终止条件
             *      区间变化
             */
            int low = 0, high = letters.length;
            while (low < high) {
                int mid = (low + high) / 2;
                if (letters[mid] <= target) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }
            return letters[low % letters.length];
        }


        private char upperBound2(char[] letters, char target) {
            /*
             * 左闭右闭区间([low, high]) 二分查找
             */
            int low = 0, high = letters.length - 1;
            while (low <= high) {
                int mid = (low + high) / 2;
                if (letters[mid] <= target) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            return letters[low % letters.length];
        }
    }
}
